home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / bipl.zip / PROGS.ZIP / TURING.ICN < prev    next >
Text File  |  1992-09-28  |  5KB  |  172 lines
  1. ############################################################################
  2. #
  3. #    File:     turing.icn
  4. #
  5. #    Subject:  Program to simulate a Turing machine
  6. #
  7. #    Author:   Gregg M. Townsend
  8. #
  9. #    Date:     June 10, 1988
  10. #
  11. ###########################################################################
  12. #
  13. #     This program simulates the operation of an n-state Turing machine,
  14. #  tracing all actions.  The machine starts in state 1 with an empty tape.
  15. #
  16. #     A description of the Turing machine is read from the file given as a
  17. #  command-line argument, or from standard input if none is specified.
  18. #  Comment lines beginning with '#' are allowed, as are empty lines.
  19. #
  20. #     The program states must be numbered from 1 and must appear in order.
  21. #  Each appears on a single line in this form:
  22. #
  23. #      sss.  wdnnn  wdnnn
  24. #
  25. #  sss is the state number in decimal.  The wdnnn fields specify the
  26. #  action to be taken on reading a 0 or 1 respectively:
  27. #
  28. #      w   is the digit to write (0 or 1)
  29. #      d   is the direction to move (L/l/R/r, or H/h to halt)
  30. #      nnn is the next state number (0 if halting)
  31. #
  32. #  Sample input file:
  33. #
  34. #      1. 1r2 1l3
  35. #      2. 1l1 1r2
  36. #      3. 1l2 1h0
  37. #
  38. #     One line is written for each cycle giving the cycle number, current
  39. #  state, and an image of that portion of the tape that has been visited
  40. #  so far.  The current position is indicated by reverse video (using
  41. #  ANSI terminal escape sequences).
  42. #
  43. #     Input errors are reported to standard error output and inhibit
  44. #  execution.
  45. #
  46. #     Bugs:
  47. #
  48. #     Transitions to nonexistent states are not detected.
  49. #  Reverse video should be parameterizable or at least optional.
  50. #  There is no way to limit the number of cycles.
  51. #  Infinite loops are not detected.  (Left as an exercise... :-)
  52. #
  53. #  Reference:
  54. #
  55. #     Scientific American, August 1984, pp. 19-23.  A. K. Dewdney's
  56. #  discussion of "busy beaver" turing machines in his "Computer
  57. #  Recreations" column motivated this program.  The sample above
  58. #  is the three-state busy beaver.
  59. #
  60. ############################################################################
  61. #
  62. #  Links: options
  63. #
  64. ############################################################################
  65.  
  66. link options
  67.  
  68. record action (wrt, mov, nxs)
  69.  
  70. global machine, lns, lno, errs
  71. global cycle, tape, posn, state, video
  72.  
  73. procedure main(args)
  74.    local opts
  75.  
  76.    opts := options(args,"v")
  77.    video := \opts["v"]
  78.  
  79.    rdmach(&input)            # read machine description
  80.    if errs > 0 then stop("[execution suppressed]")
  81.    lns := **machine            # initialize turing machine
  82.    tape := "0"
  83.    posn := 1
  84.    cycle := 0
  85.    state := 1
  86.    while state > 0 do {        # execute
  87.       dumptape()
  88.       transit(machine[state][tape[posn]+1])
  89.       cycle +:= 1
  90.    }
  91.    dumptape()
  92. end
  93.  
  94. #  dumptape - display current tape contents on screen
  95.  
  96. procedure dumptape()
  97.    if cycle < 10 then writes(" ")
  98.    writes(cycle,". [",right(state,lns),"] ",tape[1:posn])
  99.    if \video then write("\e[7m",tape[posn],"\e[m",tape[posn + 1:0])
  100.    else {
  101.       write(tape[posn:0])
  102.       write(repl(" ",6 + *state + posn),"^")
  103.       }
  104. end
  105.  
  106.  
  107. #  transit (act) - transit to the next state performing the given action
  108.  
  109. procedure transit(act)
  110.    tape[posn] := act.wrt
  111.    if act.mov == "R" then {
  112.       posn +:= 1
  113.       if posn > *tape then tape ||:= "0"
  114.       }
  115.    else if act.mov == "L" then {
  116.       if posn = 1 then tape := "0" || tape
  117.       else posn -:= 1
  118.       }
  119.    state := act.nxs
  120.    return
  121. end
  122.  
  123. #  rdmach (f) - read machine description from the given file
  124.  
  125. procedure rdmach(f)
  126.    local nstates, line, a0, a1,n
  127.  
  128.    machine := list()
  129.    nstates := 0
  130.    lno := 0
  131.    errs := 0
  132.    while line := trim(read(f),' \t') do {
  133.       lno +:= 1
  134.       if *line > 0 & line[1] ~== "#"
  135.          then line ? {
  136.               tab(many(' \t'))
  137.               n := tab(many(&digits)) | 0
  138.               if n ~= nstates + 1 then warn("sequence error")
  139.             nstates := n
  140.             tab(many('. \t'))
  141.               a0 := tab(many('01LRHlrh23456789')) | ""
  142.               tab(many(' \t'))
  143.               a1 := tab(many('01LRHlrh23456789')) | ""
  144.               pos(0) | (warn("syntax error") & next)
  145.               put(machine,[mkact(a0),mkact(a1)])
  146.             }
  147.    }
  148.    lno := "<EOF>"
  149.    if *machine = errs = 0 then warn("no machine!")
  150.    return
  151. end
  152.  
  153. #  mkact (a) - construct the action record specified by the given string
  154.  
  155. procedure mkact(a)
  156.    local w, m, n
  157.  
  158.    w := a[1] | "9"
  159.    m := map(a[2],&lcase,&ucase) | "X"
  160.    (any('01',w) & any('LRH',m)) | warn("syntax error")
  161.    n := integer(a[3:0]) | (warn("bad nextstate"), 0)
  162.    return action (w, m, n)
  163. end
  164.  
  165. #  warn (msg) - report an error in the machine description
  166.  
  167. procedure warn(msg)
  168.    write(&errout, "line ", lno, ": ", msg)
  169.    errs +:= 1
  170.    return
  171. end
  172.